7. 小牛牛超市选品

题目内容

牛牛在超市采购商品，每件商品有对应价格（均为正整数）。给定预算 limit，要求选出连续一段商品，满足两条约束：

• 这段商品总价格严格大于 limit
• 这段商品中最贵商品价格 ≤ limit

请找出满足以上两条规则的最短连续商品长度；不存在合法区间输出 0。

约束条件：

• 0 < limit < 100
• 0 < n ≤ 10
• 0 < A_i ≤ 10

输入描述

• 参数 1：商品数量 n
• 参数 2：预算上限 limit
• 参数 3：商品价格数组，数组元素代表每件商品价格 A_i

输出描述

合法最短区间长度；无合法区间输出 0。

样例

样例 1

输入

6 7
2 3 1 2 4 3

输出

3

说明：

• [4,3] 的和为 7，不满足严格大于 7，作废
• [2,4,3] 的和为 9>7，最大值 4 ≤ 7，长度 3
• [3,1,2,4] 的和为 10>7，长度 4

最短合法长度为 3。

样例 2

输入

3 11
1 2 3

输出

0

说明： 不满足 limit 约束。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const limit = Number(input.split(' ')[1]);
    rl.on('line', (input) => {
        const arr = input.split(' ').map(v => parseInt(v));
        let left = 0;
        let right = 0;
        let min = Infinity;
        function isYes(l, r) {
            let res = 0;
            for(let i=l; i<=r; i++) {
                if (arr[i] > limit) {
                    return false;
                } else {
                    res += arr[i];
                }
            }
            if (res > limit) {
                return true;
            } else {
                return false;
            }
        }
        while(left <= right && right < arr.length) {
            if (isYes(left, right)) {
                min = Math.min(min, right-left+1);
                // console.log(min, left, right);
                left++;
            } else {
                right++;
            }
        }
        console.log(min === Infinity ? 0 : min);
    })
})